#!/bin/env python

import csv
from pysqlite2 import dbapi2 as sqlite
from collections import deque

def full_set_states (cursor, num_options):
    for i in range(2**num_options):
    	cursor.execute('INSERT INTO states (state_number, is_feasible) VALUES (?, ?)', (i, 1))
    	
    return deque(range(2**num_options))

def and_values (value_1, value_2, full_set=None): #AND_VALUES
	if full_set:
		full_set = deque(full_set)
	if isinstance(value_1,int) and isinstance(value_2,deque): #int, deque
		sub_set = deque()
		value_2 = deque(value_2)
		while len(value_2) > 0:
			value = value_2.pop()
			if value & value_1 == value_1:
				sub_set.append(value)
		return sub_set
	if isinstance(value_1,deque) and isinstance(value_2,int): #deque, int
		return and_values(value_2,value_1,full_set)
	if isinstance(value_1,deque) and isinstance(value_2,deque): #deque, deque
		value_1 = deque(value_1)
		value_2 = deque(value_2)
		sub_set = deque()
		while len(value_1) > 0:
			value = value_1.pop()
			for check_value in value_2:
				if check_value == value:
					sub_set.append(value)
		return sub_set
	if isinstance(value_1,int) and isinstance(value_2,int): #int, int
		return and_values(and_values(value_1,full_set),and_values(value_2,full_set),full_set)
		
def or_values (value_1, value_2, full_set=None): #OR_VALUES
	if full_set:
		full_set = deque(full_set)
	if isinstance(value_1,deque) and isinstance(value_2,deque):
		value_1 = deque(value_1)
		value_2 = deque(value_2)
		sum_states = deque()
		while len(value_1) > 0:
			sum_states.append(value_1.pop())
		while len(value_2) > 0:
			value = value_2.pop()
			value_found = None
			for sum_states_value in sum_states:
				if value == sum_states_value:
					value_found = 1
			if not value_found:
				sum_states.append(value)
		return sum_states
	elif isinstance(value_1,deque) and isinstance(value_2,int):
		return or_values(value_1,and_values(value_2,full_set),full_set)
	elif isinstance(value_1,int) and isinstance(value_2,deque):
		return or_values(value_2,value_1,full_set)
	elif isinstance(value_1,int) and isinstance(value_2,int):
		return of_values(and_values(value_1,full_set),and_values(value_2,full_set),full_set)

def not_values (values, full_set):
	full_set = deque(full_set)
	if isinstance(values,deque) and isinstance(full_set,deque):
		for value in values:
			print '(VAL) ',value
			full_set.remove(value)
		return full_set 
	if isinstance(values,int) and isinstance(full_set,deque):
		return not_values(and_values(values,full_set,full_set),full_set)

def find_matching (rules, states):
	row_stack = deque()
	for value in rules:
		if value in option_short2option:
			row_stack.append(2**option_short2option[value])
			row_stack.append(and_values(row_stack.pop(), states, states))
			#print option_short2option[value]
		elif value.lower() == 'if':
			if len(row_stack) == 1 or not row_stack:
				print 'IF requires two values on the stack'
			else:
				temp_value = row_stack.pop()
				row_stack.append(not_values(row_stack.pop(),states))
				row_stack.append(temp_value)
				row_stack.append(and_values(row_stack.pop(),row_stack.pop(),states))
				row_stack.append(not_values(row_stack.pop(),states))
				print 'IF: ',row_stack
		elif value.lower() == 'and':
			if len(row_stack) == 1 or not row_stack:
				print 'AND requires two values on the stack'
			else:
				row_stack.append(and_values(row_stack.pop(), row_stack.pop(),states))
		elif value.lower() == 'or':
			if len(row_stack) == 1 or not row_stack:
				print 'OR requires two values on the stack'
			else:
				row_stack.append(or_values(row_stack.pop(), row_stack.pop(),states))
		elif value.lower() == 'not':
			if not row_stack:
				print 'NOT requires one value on the stack'
			else:
				row_stack.append(not_values(row_stack.pop(),states))
	return row_stack.pop()

def is_seq_stable(cursor, original_dm, original_state, current_state = None, last_dm_to_move = None):
	if not current_state and not last_dm_to_move:
	    cursor.execute('SELECT r.dm, p2.state \
		FROM preferences AS p1, preferences AS p2, reachable_states AS r \
		WHERE \
		    p1.state = %s AND \
		    p1.dm = r.dm AND \
		    p1.state = r.source_state AND \
		    p2.state = r.dest_state AND \
		    r.dm = %s AND \
		    p2.state_rank < p1.state_rank AND \
		    p1.dm = p2.dm' % (original_state, original_dm))

	else:
	    cursor.execute('SELECT state_rank FROM preferences AS p \
		    WHERE p.dm = %s AND \
		    p.state = %s' % (original_dm, current_state))
	    current_state_rank = cursor.fetchone()[0]
	    cursor.execute('SELECT state_rank FROM preferences AS p \
		    WHERE p.dm = %s AND \
		    p.state = %s' % (original_dm, original_state))
	    original_state_rank = cursor.fetchone()[0]
	    if current_state_rank >= original_state_rank:
		    return True
	    cursor.execute('SELECT r.dm, p2.state \
		FROM preferences AS p1, preferences AS p2, reachable_states AS r \
		WHERE \
		    p1.state = %s AND \
		    p1.dm = r.dm AND \
		    p1.state = r.source_state AND \
		    p2.state = r.dest_state AND \
		    r.dm != %s AND \
		    r.dm != %s AND \
		    p2.state_rank < p1.state_rank AND \
		    p1.dm = p2.dm' % (current_state, last_dm_to_move, original_dm))
	uis = cursor.fetchall()

	if len(uis) > 0:
	    responses = []
	    for ui in uis:
		    responses.append(is_seq_stable(cursor, original_dm, original_state, ui[1], ui[0]))
		    ultimate_response = False
	    for response in responses:
		if response:
			ultimate_response = True
	    return ultimate_response
	elif len(uis) == 0:
		if not current_state and not last_dm_to_move:
			return True
		else:
		    cursor.execute('SELECT state_rank FROM preferences AS p \
			    WHERE p.dm = %s AND \
			    p.state = %s' % (original_dm, current_state))
		    current_state_rank = cursor.fetchone()[0]
		    cursor.execute('SELECT state_rank FROM preferences AS p \
			    WHERE p.dm = %s AND \
			    p.state = %s' % (original_dm, original_state))
		    original_state_rank = cursor.fetchone()[0]
		    if current_state_rank >= original_state_rank:
			    return True
		    else:
			    return False

def is_gmr_stable(cursor, original_dm, original_state, current_state = None, last_dm_to_move = None):
	if not current_state and not last_dm_to_move:
	    cursor.execute('SELECT r.dm, p2.state \
		FROM preferences AS p1, preferences AS p2, reachable_states AS r \
		WHERE \
		    p1.state = %s AND \
		    p1.dm = r.dm AND \
		    p1.state = r.source_state AND \
		    p2.state = r.dest_state AND \
		    r.dm = %s AND \
		    p2.state_rank < p1.state_rank AND \
		    p1.dm = p2.dm' % (original_state, original_dm))

	else:
	    cursor.execute('SELECT state_rank FROM preferences AS p \
		    WHERE p.dm = %s AND \
		    p.state = %s' % (original_dm, current_state))
	    current_state_rank = cursor.fetchone()[0]
	    cursor.execute('SELECT state_rank FROM preferences AS p \
		    WHERE p.dm = %s AND \
		    p.state = %s' % (original_dm, original_state))
	    original_state_rank = cursor.fetchone()[0]
	    if current_state_rank >= original_state_rank:
		    return True
	    cursor.execute('SELECT r.dm, r.dest_state \
		FROM reachable_states AS r \
		WHERE \
		    r.source_state = %s AND \
		    r.dm != %s AND \
		    r.dm != %s' % (current_state, last_dm_to_move, original_dm))
	moves = cursor.fetchall()

	if len(moves) > 0:
	    responses = []
	    for move in moves:
		    responses.append(is_seq_stable(cursor, original_dm, original_state, move[1], move[0]))
		    ultimate_response = False
	    for response in responses:
		if response:
			ultimate_response = True
	    return ultimate_response
	elif len(moves) == 0:
		if not current_state and not last_dm_to_move:
			return True
		else:
		    cursor.execute('SELECT state_rank FROM preferences AS p \
			    WHERE p.dm = %s AND \
			    p.state = %s' % (original_dm, current_state))
		    current_state_rank = cursor.fetchone()[0]
		    cursor.execute('SELECT state_rank FROM preferences AS p \
			    WHERE p.dm = %s AND \
			    p.state = %s' % (original_dm, original_state))
		    original_state_rank = cursor.fetchone()[0]
		    if current_state_rank >= original_state_rank:
			    return True
		    else:
			    return False

def is_smr_stable(cursor, original_dm, original_state, current_state = None, last_dm_to_move = None):
	if not current_state and not last_dm_to_move:
	    cursor.execute('SELECT r.dm, p2.state \
		FROM preferences AS p1, preferences AS p2, reachable_states AS r \
		WHERE \
		    p1.state = %s AND \
		    p1.dm = r.dm AND \
		    p1.state = r.source_state AND \
		    p2.state = r.dest_state AND \
		    r.dm = %s AND \
		    p2.state_rank < p1.state_rank AND \
		    p1.dm = p2.dm' % (original_state, original_dm))

	else:
	    cursor.execute('SELECT state_rank FROM preferences AS p \
		    WHERE p.dm = %s AND \
		    p.state = %s' % (original_dm, current_state))
	    current_state_rank = cursor.fetchone()[0]
	    cursor.execute('SELECT state_rank FROM preferences AS p \
		    WHERE p.dm = %s AND \
		    p.state = %s' % (original_dm, original_state))
	    original_state_rank = cursor.fetchone()[0]
	    if current_state_rank >= original_state_rank:
	    	cursor.execute('SELECT p.state \
			FROM preferences AS p, reachable_states AS r \
			WHERE \
				r.dm = %s AND \
				p.dm = r.dm AND \
				r.source_state = %s AND \
				r.dest_state = p.state AND \
				p.state_rank <  %s' % (original_dm, current_state, original_state_rank))
		if len(cursor.fetchall()) == 0:
		    return True
	    cursor.execute('SELECT r.dm, r.dest_state \
		FROM reachable_states AS r \
		WHERE \
		    r.source_state = %s AND \
		    r.dm != %s AND \
		    r.dm != %s' % (current_state, last_dm_to_move, original_dm))
	moves = cursor.fetchall()

	if len(moves) > 0:
	    responses = []
	    for move in moves:
		    responses.append(is_seq_stable(cursor, original_dm, original_state, move[1], move[0]))
		    ultimate_response = False
	    for response in responses:
		if response:
			ultimate_response = True
	    return ultimate_response
	elif len(moves) == 0:
		if not current_state and not last_dm_to_move:
			return True
		else:
		    cursor.execute('SELECT state_rank FROM preferences AS p \
			    WHERE p.dm = %s AND \
			    p.state = %s' % (original_dm, current_state))
		    current_state_rank = cursor.fetchone()[0]
		    cursor.execute('SELECT state_rank FROM preferences AS p \
			    WHERE p.dm = %s AND \
			    p.state = %s' % (original_dm, original_state))
		    original_state_rank = cursor.fetchone()[0]
		    if current_state_rank >= original_state_rank:
			    cursor.execute('SELECT p.state \
				    FROM preferences AS p, reachable_states AS r \
				    WHERE \
					    r.dm = %s AND \
					    p.dm = r.dm AND \
					    r.source_state = %s AND \
					    r.dest_state = p.state AND \
					    p.state_rank <  %s' % (original_dm, current_state, original_state_rank))
			    if len(cursor.fetchall()) == 0:
				return True
		    else:
			    return False

def output_pref_vectors (dms, options, option2option_short, pref_vectors, output_filename = 'pref_vectors.csv'):
	writer = csv.writer(open(output_filename, 'wb'))
	first_line = deque()
	first_line.append("Preference Vectors")
	writer.writerow(first_line)
	writer.writerow(deque()) #writes a blank line
	#cursor.execute('SELECT name_long, state_rank, state_number FROM preferences, dms, states where states.state_number = preferences.state and preferences.dm = dms.id order by dms.id')
	#print '\n\n\n', cursor.fetchall(), '\n\n\n'
	cursor.execute('SELECT \
		name_long, state_rank, state_number \
		FROM dms, states, preferences \
		WHERE dms.id = preferences.dm AND \
		preferences.state = states.state_number \
		ORDER BY dms.id, state_rank, states.id')
	#print cursor.fetchall()
	cursor.execute('SELECT id, name_long FROM dms')
	for dm in cursor.fetchall():
		#print dm[0]
		cursor.execute('SELECT \
			state_rank, state, state_number \
			FROM states, preferences \
			WHERE preferences.dm = %s AND \
			preferences.state = states.id \
			order by state_rank, state_number' % dm[0])
		state_preferences = cursor.fetchall()
		cursor.execute('SELECT option_number, name_long, option_long FROM options, dms where dms.id = options.dm')
		options = cursor.fetchall()
		print options

		#lines = {}
		lines = [[] for i in range(len(options) + 6)]
		lines[0] = deque()
		lines[0].append(dm[1] + '(Focal DM):')
		lines[0].append('Options:')
		for i in range(len(options)):
			lines[i+1] = deque()
			lines[i+1].append(options[i][1])
			lines[i+1].append(options[i][2])
		lines[1+len(options)].append(' ')
		lines[1+len(options)].append('UIs')
		lines[2+len(options)].append(' ')
		lines[2+len(options)].append('Nash')
		lines[3+len(options)].append(' ')
		lines[3+len(options)].append('GMR')
		lines[4+len(options)].append(' ')
		lines[4+len(options)].append('SMR')
		lines[5+len(options)].append(' ')
		lines[5+len(options)].append('SEQ')
		last_rank = 0
		for state in state_preferences:
			if state[0] != last_rank:
				for i in range(len(options) + 6):
				    lines[i].append(' ')
				last_rank = state[0]
			lines[0].append(state[2])
			for i in range(len(options)):
				if state[2] & 2**options[i][0] == 0:
					lines[i+1].append('N')
				elif state[2] & 2**options[i][0] > 0:
					lines[i+1].append('Y')

			#print state[1], dm[0]
			cursor.execute('SELECT s.state_number, p1.state_rank, p2.state_rank \
			    FROM preferences AS p1, preferences AS p2, reachable_states AS r, states AS s \
			    WHERE \
			    	p1.state = %s AND \
				p1.dm = %s AND \
				p1.state = r.source_state AND \
				p2.state = r.dest_state AND \
				r.dm = %s AND \
				p2.state_rank < p1.state_rank AND \
				p1.dm = p2.dm AND \
				s.id = p2.state' % (state[1], dm[0], dm[0]))
			uis = cursor.fetchall()
			#print 'UIs: ', uis

			if len(uis) > 1:
				ui_list = []
				for i in uis:
					ui_list.append(str(i[0]))
				lines[1+len(options)].append(', '.join(ui_list))
			elif len(uis) == 1:
			    lines[1+len(options)].append(uis[0][0])
			else:
			    lines[1+len(options)].append(' ')
			# Attempt to classify Nash stability
			cursor.execute('SELECT 1 \
			    FROM preferences AS p1, preferences AS p2, reachable_states AS r1, states AS s \
			    WHERE \
			    	p1.state = %s AND \
				p1.dm = %s AND \
				p1.state = r1.source_state AND \
				r1.dm = %s AND \
				p2.state = r1.dest_state AND \
				p2.state_rank < p1.state_rank AND \
				p1.dm = p2.dm AND \
				s.id = p2.state' % (state[1], dm[0], dm[0]))
			are_uis = cursor.fetchall()
			if len(are_uis) > 0:
				lines[2+len(options)].append('N')
			else:
				lines[2+len(options)].append('Y')

			# Attempt to classify GMR stability
			if is_gmr_stable(cursor, dm[0], state[1]):
				lines[3+len(options)].append('Y')
			else:
				lines[3+len(options)].append('N')

			# Attempt to classify SMR stability
			if is_smr_stable(cursor, dm[0], state[1]):
				lines[4+len(options)].append('Y')
			else:
				lines[4+len(options)].append('N')

			# Attempt to classify SEQ stability
			if is_seq_stable(cursor, dm[0], state[1]):
				lines[5+len(options)].append('Y')
			else:
				lines[5+len(options)].append('N')


		#print 'PRINT!: ', lines
		writer.writerows(lines)
		writer.writerow([])

	    	
	    	


connection = sqlite.connect(':memory:')
#connection = sqlite.connect('out.db')
cursor = connection.cursor()

# Create tables
cursor.execute ('CREATE TABLE dms (id INTEGER PRIMARY KEY, name_short VARCHAR(10), name_long VARCHAR(20))')

cursor.execute ('CREATE TABLE options (id INTEGER PRIMARY KEY, dm INTEGER REFERENCES dms (id), option_number INTEGER, option_short VARCHAR(10), option_long VARCHAR(20))')

cursor.execute ('CREATE TABLE states (id INTEGER PRIMARY KEY, state_number INTEGER, is_feasible BOOLEAN)')

cursor.execute ('CREATE TABLE preferences (id INTEGER PRIMARY KEY, dm INTEGER REFERENCES dms (id), state_rank INTEGER, state INTEGER REFERENCES states (id))')

cursor.execute ('CREATE TABLE reachable_states (id INTEGER PRIMARY KEY, dm INTEGER REFERENCES dms (id), source_state INTEGER REFERENCES states (id), dest_state INTEGER REFERENCES states (id))')

conflict = csv.reader(open('conflict.csv', 'rb'))

dms = {}
options = []
option_short2option = {}
option2option_short = {}
dm_options = {}
last_dm = ''
for index, row in enumerate(conflict):
	if index != 0 and row: #ie, row is not blank
	    if row[0] not in dms and row[0]: #ie, row[0] is not blank
		cursor.execute('INSERT INTO dms (name_short, name_long) VALUES (?, ?)', (row[0], row[1]))
		dms[row[0]] = row[1]
		#last_dm = row[0]
		last_dm = cursor.lastrowid
	    cursor.execute('INSERT INTO options (dm, option_number, option_short, option_long ) VALUES (?, ?, ?, ?)', (last_dm, len(options), row[2], row[3]))
	    option_short2option[row[2]] = len(options)
	    option2option_short[len(options)] = row[2]
	    if last_dm not in dm_options:
		dm_options[last_dm] = {}
	    dm_options[last_dm][len(dm_options[last_dm])] = len(options)
	    options.append({0 : last_dm, 1 : row[1], 2 : row[2], 3 : row[3]})
print 'Decision Makers: ', dms, '\n\nOption_short to Option array: ', option_short2option, '\n\nOption to Option_short array: ', option2option_short, '\n\nDM Options: ', dm_options, '\n\nOptions: ', options, '\n'

full_set_states = full_set_states(cursor, len(options))

print 'States: ', full_set_states

print 'There are ', len(full_set_states), ' states.\n'

infeasible = csv.reader(open('infeasible.csv', 'rb'))

feasible_states = full_set_states
infeasible_states = deque()
for index, row in enumerate(infeasible):
	if index != 0 and row: #ie, row is not blank
		infeasible_states.extend(find_matching(row, full_set_states))
		print 'Infeasible States: ', infeasible_states
infeasible_states = deque(set(infeasible_states))
print '(SET) Infeasible States: ', infeasible_states
print 'Full Set of States: ', full_set_states
feasible_states = not_values(infeasible_states,full_set_states)
print 'Feasible states: ', feasible_states
print 'There are ', len(feasible_states), ' feasible states.\n'

if infeasible_states:
    print infeasible_states
    in_var = '(' + ', '.join(['?'] * len(infeasible_states)) + ')'
    #print in_var
	    
    cursor.execute('UPDATE states SET is_feasible = 0 WHERE state_number IN %s' % in_var, infeasible_states)


preferences = csv.reader(open('preferences.csv', 'rb'))
#preferences = csv.reader(open('preferences_hypergame.csv', 'rb'))

# Here we have preferences defined for each player. First code for just one player, then add outer loop to deal with multiple players.

current_dm = None

preference_vectors = {}

for index, row in enumerate(preferences):
	if index != 0 and row: #ie, row not blank
	    print row
	    if row[0] != current_dm and row[0]:
		if current_dm:
		    #Set data structures for the previous dm
		    preference_vectors[current_dm] = states_stack
	    	current_dm = row[0]
		states_stack = deque()
		states_stack_2 = deque()
		states_stack.append(deque(feasible_states))
	    while states_stack:
		states = states_stack.pop()
		#print row
		matching_states = find_matching(row, states)
		#print 'Matching States: ', matching_states 
		other_states = not_values(matching_states,states)
		if other_states:
		    states_stack_2.appendleft(other_states)
		if matching_states:
		    states_stack_2.appendleft(matching_states)

	    states_stack_2, states_stack = states_stack, states_stack_2

preference_vectors[current_dm] = states_stack

for dm in dms:
	if dm in preference_vectors:
	    cursor.execute("select id from dms where name_short = ('%s')" % dm)
	    dm_id = cursor.fetchone()[0]
	    pref_vector = preference_vectors[dm]
	    for i in range(len(pref_vector)):
		equal_states = pref_vector[i]
		print equal_states
	    	for state in equal_states:
		    cursor.execute('SELECT id FROM states WHERE state_number = %s' % state)
		    state_id = cursor.fetchone()[0]
		    cursor.execute('INSERT INTO preferences (dm, state_rank, state) VALUES (?, ?, ?)', (dm_id, i, state_id))
	
#print 'Preference Vector: ', states_stack
print 'Preference Vectors: ', preference_vectors

# Determine the reachable list of states for each DM
cursor.execute('INSERT INTO reachable_states (dm, source_state, dest_state) \
	SELECT \
		dms.id, s1.id, s2.id \
	FROM \
		dms, \
		states AS s1, \
		states AS s2, \
		options \
	WHERE \
	dms.id = options.dm AND \
	s1.is_feasible = 1 AND \
	s1.id != s2.id AND \
	s2.is_feasible = 1 \
	GROUP BY dms.id, s1.id, s2.id \
	HAVING (~(s1.state_number & s2.state_number)) & (s1.state_number | s2.state_number) & (~(sum(1<<(options.option_number)))) = 0')


	#implements XOR, to find out which bits are changed between states. Then we compare with 1 shifted by the option number (to produce 2^n) which tells us if the change was due entirely to changing the one option number.

#cursor.execute('SELECT * FROM dms')
#for dm in cursor.fetchall():
	#cursor.execute('SELECT * FROM options WHERE dm = %s' % dm)
	#for option in cursor.fetchall():

	    #cursor.execute('SELECT * FROM states WHERE is_feasible = 1')
	    #for state in cursor.fetchall():
		    #cursor.execute('INSERT INTO reachable_states (dm, source_state, dest_state

cursor.execute('SELECT * FROM dms')
print '\nDMs: ', cursor.fetchall()

cursor.execute('SELECT * FROM options')
print '\nOptions: ', cursor.fetchall()

cursor.execute('SELECT * FROM states')
print '\nStates: ', cursor.fetchall()

cursor.execute('SELECT * FROM preferences')
print '\nPreferences: ', cursor.fetchall()

cursor.execute('SELECT * FROM reachable_states')
print '\nReachable States: ', cursor.fetchall()

output_pref_vectors(dms, options, option2option_short, preference_vectors)
